package com.fe.class09;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description 快慢指针练习
 * 1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
 * 2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
 * 3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
 * 4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
 * @Author sosuke :-)
 * @Date 2022/1/24 20:23
 */
public class Code01_LinkedListMid {
    public static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
     */
    public static Node midOrUpMidNode(Node head) {
        // 节点数0、1、2  都返回head
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        // 节点数>=3
        Node slow = head;
        Node fast = head;
        // 或下面这种
        // head--->slow--->fast  规律：返回中点或上中点，slow在中间
        // Node slow = head.next;
        // Node fast = head.next.next;

        // slow走一步，fast走两步
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
     */
    public static Node midOrDownMidNode(Node head) {
        // 节点数0、1  都返回head
        if (head == null || head.next == null) {
            return head;
        }
        // 节点数>=2  head--->slow、fast  规律：返回中点或下中点，fast往前一步
        Node slow = head.next;
        Node fast = head.next;
        // slow走一步，fast走两步
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
     */
    public static Node midOrUpMidPreNode(Node head) {
        // 节点数0、1、2  都返回null
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        // 节点数>=3  head、slow--->node--->fast  规律：返回(中点或上中点)的前一个，slow往前一步
        Node slow = head;
        Node fast = head.next.next;
        // slow走一步，fast走两步
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
     */
    public static Node midOrDownMidPreNode(Node head) {
        // 节点数0、1  都返回null
        if (head == null || head.next == null) {
            return null;
        }
        // 节点数2  返回head
        if (head.next.next == null) {
            return head;
        }
        // 节点数>=3  head、slow--->fast--->node  规律：返回(中点或下中点)的前一个，slow、fast往前一步
        Node slow = head;
        Node fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 使用容器的方式来解决
    public static class TestLinkedListMid {
        /**
         * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
         */
        public static Node testMidOrUpMidNode(Node head) {
            if (head == null) return null;
            List<Node> arrList = initialContainer(head);
            return arrList.get((arrList.size() - 1) / 2);
        }

        /**
         * 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
         */
        public static Node testMidOrDownMidNode(Node head) {
            if (head == null) return null;
            List<Node> arrList = initialContainer(head);
            return arrList.get(arrList.size() / 2);
        }

        /**
         * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
         */
        public static Node testMidOrUpMidPreNode(Node head) {
            // 节点数0、1、2
            if (head == null || head.next == null || head.next.next == null) {
                return null;
            }
            List<Node> arrList = initialContainer(head);
            return arrList.get((arrList.size() - 1) / 2 - 1);
        }

        /**
         * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
         */
        public static Node testMidOrDownMidPreNode(Node head) {
            // 节点数0、1
            if (head == null || head.next == null) {
                return null;
            }
            List<Node> arrList = initialContainer(head);
            return arrList.get(arrList.size() / 2 - 1);
        }

        private static List<Node> initialContainer(Node head) {
            List<Node> list = new ArrayList<>();
            while (head != null) {
                list.add(head);
                head = head.next;
            }
            return list;
        }
    }

    public static void main(String[] args) {
        int testTime = 100000;
        int maxSize = 15;
        int maxValue = 100;
        for (int i = 0; i < testTime; i++) {
            Node node = generateRandomLinkedList(maxSize, maxValue);
            Node ans1 = midOrUpMidNode(node);
            Node ans2 = TestLinkedListMid.testMidOrUpMidNode(node);
            if (!isNodeEqual(ans1, ans2)) {
                System.out.println("testMidOrUpMidNode Fuck");
                printLinkedList(node);
                System.out.println("ans1 = " + ans1);
                System.out.println("ans2 = " + ans2);
                return;
            }
            ans1 = midOrDownMidNode(node);
            ans2 = TestLinkedListMid.testMidOrDownMidNode(node);
            if (!isNodeEqual(ans1, ans2)) {
                System.out.println("testMidOrDownMidNode Fuck");
                printLinkedList(node);
                System.out.println("ans1 = " + ans1);
                System.out.println("ans2 = " + ans2);
                return;
            }

            ans1 = midOrUpMidPreNode(node);
            ans2 = TestLinkedListMid.testMidOrUpMidPreNode(node);
            if (!isNodeEqual(ans1, ans2)) {
                System.out.println("testMidOrUpMidPreNode Fuck");
                printLinkedList(node);
                System.out.println("ans1 = " + ans1);
                System.out.println("ans2 = " + ans2);
                return;
            }

            ans1 = midOrDownMidPreNode(node);
            ans2 = TestLinkedListMid.testMidOrDownMidPreNode(node);
            if (!isNodeEqual(ans1, ans2)) {
                System.out.println("testMidOrDownMidPreNode Fuck");
                printLinkedList(node);
                System.out.println("ans1 = " + ans1);
                System.out.println("ans2 = " + ans2);
                return;
            }
        }

        System.out.println("Nice");
        Node node = generateRandomLinkedList(maxSize, maxValue);
        printLinkedList(node);
        System.out.println("midOrUpMidNode(node) = " + midOrUpMidNode(node));
        System.out.println("midOrDownMidNode(node) = " + midOrDownMidNode(node));
        System.out.println("midOrUpMidPreNode(node) = " + midOrUpMidPreNode(node));
        System.out.println("midOrDownMidPreNode(node) = " + midOrDownMidPreNode(node));
    }

    /**
     * 随机生成单链表
     *
     * @return
     */
    public static Node generateRandomLinkedList(int maxSize, int maxValue) {
        // [0,maxSize]
        int size = (int) (Math.random() * (maxSize + 1));
        if (size == 0) return null;
        Node head = new Node((int) (Math.random() * (maxValue + 1)));
        size--;
        Node pre = head;
        for (int i = 0; i < size; i++) {
            Node next = new Node((int) (Math.random() * (maxValue + 1)));
            pre.next = next;
            pre = next;
        }
        return head;
    }

    /**
     * 判断两个node是否相等
     * @param n1
     * @param n2
     * @return
     */
    public static boolean isNodeEqual(Node n1, Node n2) {
        if (n1 != null && n2 != null) {
            return n1.value == n2.value;
        }

        return n1 == null && n2 == null;
    }

    /**
     * 打印单链表
     *
     * @param head
     */
    public static void printLinkedList(Node head) {
        if (null == head) {
            System.out.println("\"null\"");
            return;
        }
        Node cur = head;
        while (null != cur) {
            System.out.print(cur.value + "--->");
            System.out.print(cur.next == null ? "null" : "");
            cur = cur.next;
        }
        System.out.println();
    }

}
